Skip to main content

Game Playing

Minimax​

An opponent tried to prevent your win at every move 1944 - John von Neumann

  • A search method, maximise your position whilst minimising your opponents

Utility Function: in order to implement we need a method of measuring how good a position is

Nim - Start with a pile of tokens, at each move the player must divide the tokens into two non-empty, non-equal piles.

  • Efficiency of the search. Game trees are very big. Evaluation of positions is time-consuming
  • To reduce the number of nodes to be evaluated can explore: Alpha-beta search based on minimax. Better estimate of utility values

Minmax uses BFS

Alpha Beta Pruning

Is about reducing the size of the search tree

  • Cannot prune nodes if doing BFS. Form of pruning relies on doing a DFS
  • To maximise pruning: first expand the best children. Cannot know which ones are really best. Use heuristics for the 'best-first' ordering
  • alpha α\alpha: values are stored with each MAX node
  • beta β\beta: values are stored with each MIN node

Computerphile video

MinMax - Trying to maximise the min value. Best choice available for opponent is as bad as possible, and good as possible for the AI